Physical design is one of the steps of the IC (integrated circuit) or VLSI (very large scale integrated circuit) design process. A microelectronic IC chip is a collection of cells with electrical interconnections between them. These cells may be formed on a semiconductor substrate (for example, silicon). A cell (also interchangeably referred to herein as a sub-circuit, circuit component, or module) is one or more circuit elements grouped to perform a function. Each cell can also include further cells, sub-circuits, components or modules.
The physical design of the IC may include three tasks: portioning, placement and routing. Among these tasks, placement is an essential operation and is the portion of the physical design flow that assigns exact locations for the various sub-circuits, cells, and/or circuit components within a chip's core area.
Various computer automated design (CAD) tools are available for determining optimal placement. These are often referred to as “placers”. A common objective of a placer is to determine placement to minimize the “cost” of the chip design. For example, minimizing the total wire length (WL), or the sum of the length of all the wires in the design, is the primary objective of most existing placers. This not only helps minimize chip size, and hence cost, but also minimizes power and delay, which are proportional to the wire length. Simulated Annealing (SA) is a popular technique which has been frequently applied to solve the VLSI placement problem.
Simulated annealing is a probabilistic, iterative improvement technique used to solve many combinatorial optimization problems. Its name originated from the annealing process of gradually cooling molten metal to produce high quality metal structures. When performing simulated annealing placement, an initial placement is improved by iterative swaps and moves of the various sub-circuits, circuit components or cells. These swaps and moves may be accepted if they improve the cost. However, as circuit sizes continue to grow this simulated annealing process increasingly results in expensive runtime costs in order to achieve better placement results.